package suanfarumen;

import java.util.LinkedList;

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }

    @Override
    public String toString() {
        return "N{" +
                val +
                "," + left +
                "," + right +
                "," + next +
                '}';
    }
};


public class day8 {
    public static Node connect(Node root) {
        int layer = 0;
        int count=1;
        Node node;
        LinkedList<Node> queue = new LinkedList();
        queue.addLast(root);
        while(queue.size()!=0){
            node = queue.removeFirst();

            if(count!=(Math.pow(2,layer+1)-1)&&queue.size()!=0){
                node.next=queue.getFirst();
            }else{
                layer++;
            }
            if(node.left!=null){
                queue.addLast(node.left);
                queue.addLast(node.right);
            }
            count++;

        }
        return root;
    }

    public static void main(String[] args) {
        Node root=new Node(1,new Node(2,new Node(4,null,null,null),new Node(5,null,null,null),null),new Node(3,new Node(6,null,null,null),new Node(7,null,null,null),null),null);
        System.out.println(root);
        root = connect(root);
        System.out.println(root.next);
        System.out.println(root.left.next);
        System.out.println(root.right.next);
        System.out.println(root.left.left.next);
        System.out.println(root.left.right.next);
        System.out.println(root.right.left.next);
        System.out.println(root.right.right.next);

    }

}
